<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
               "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"
lang="utf-8" xml:lang="utf-8">
<head>
<title>mini-JVM</title>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8"/>
<link rel="stylesheet" href="style/base.css"  type="text/css" />

</head>
<body>
<div id="content">

<h1 class="title">Lab 1: mini-JVM</h1>
Due time: to be announced, but we advise you to start as early as possible


<div id="outline-container-1" class="outline-2">
<h2 id="sec-1">Introduction </h2>
<div class="outline-text-2" id="text-1">

<p>This lab requires you to write a virtual machine (an interpreter)
for a small
stack-based low-level language called mini-bytecode, just like the
well-known Java bytecode.
</p>
</div>

</div>

<div id="outline-container-2" class="outline-2">
<h2 id="sec-2">Requirement </h2>
<div class="outline-text-2" id="text-2">

<p>You should <a href="lab1.rar">download</a> this package, in which
we have offered you a code skeleton. Here is a brief discription of
the files:
<ul>
<li><code>call-main.sml</code>: the entry point of whole program
<li><code>main.sig, main.sml</code>: control all parts of the mini-JVM
<li><code>file-reader.sig, file-reader.sml</code>: read as input a bytecode file, to form a char list
<li><code>bytecode.sig, bytecode.fun</code>: the internal representation of a bytecode file
<li><code>parser.sig, parser.fun</code>: parse the input char list, and form
  the internal representation of a bytecode file
<li><code>jvm.sig, jvm.fun</code>: the mini-JVM execution engine
<li><code>sources.cm, sources.mlb, jvm.mlb</code>: various makefiles
<li><code>test/*</code>: some test cases
<li><code>util/*</code>: various utility library
</ul>

<p>First, compile the sources with MLton:
<pre>
mlton -verbose 2 jvm.mlb
</pre>
which would normally produce an executable <code>jvm.exe</code> or <code>jvm</code>
(If you don't produce the executable, contact us!). And now you may try to
run a test case and see the result by typing:
<pre>
jvm -verbose 2 test/gcd.class
</pre>
You may see the execution information ended with an exeception
<pre>
unhandled exeception: AddYourCode
</pre>
which means that you must add your code at some point (as we'd point out
a little later) to make the executable run correctly. (Question: what
other options jvm supports besides <code>-verbose</code>?)

<p>
The high-level execution flow is: first, <code>file-reader</code>
read from a text file and return its content as a list of char; and
then <code>parser</code> parses the char list into <code>bytecode</code>, and
finally, the <code>jvm</code> executes the internal representation of 
bytecode and print out the final result to standard out.

Your job is to finish 
the files <code>"bytecode.fun", "parser.fun"</code> and 
<code>"jvm.fun"</code>. The code you should modify looks like:
<pre>
raise AddYourCode
</pre>
So you should find all place marked as this and replace them
with your code.

<p>
We have also provided you two test cases:
<code>"gcd.class"</code> and <code>"sum.class"</code>, as can be 
found in the <code>"test/"</code>
sub-directory. The correct output should be <code>"Result:4"</code> 
and <code>"Result:55"</code> separately. After you finish all the files, 
you can compile by <code>"CM.make "sources.cm";"</code> using SML/NJ 
or by <code>"mlton jvm.mlb" </code>
in command-line using MLton to test your code.

</div>

</div>

<div id="outline-container-3" class="outline-2">
<h2 id="sec-3">mini-Bytecode Syntax </h2>
<div class="outline-text-2" id="text-3">

<p>The mini-Bytecode language is stack-based, supporting 
following instructions, in which <i>i</i> is an integer between 0 and 127.
</p>
<dl>
<dt>pop</dt><dd>
pop top element off the stack 
</dd>
<dt>add</dt><dd>
add
</dd>
<dt>sub</dt><dd>
subtract
</dd>
<dt>swap</dt><dd>
swap top two elements
</dd>
<dt>push <i>i</i></dt><dd>
push value <i>i</i> onto stack
</dd>
<dt>jump <i>i</i></dt><dd>
jump to instruction <i>i</i>
</dd>
<dt>jeq <i>i</i></dt><dd>
jump to <i>i</i>, if top two equal
</dd>
<dt>jlt <i>i</i></dt><dd>
jump to <i>i</i>, if top two less
</dd>
<dt>store <i>i</i></dt><dd>
save top element as variable <i>i</i> and pop off
</dd>
<dt>load <i>i</i></dt><dd>
load variable <i>i</i> onto stack
</dd>
<dt>stop</dt><dd>
stop execution
</dd>
</dl>


<p>
Program is a sequence of these instructions. For example, here 
is a program to find the greatest common
divider of 12 and 8.
</p>



<pre class="example">
0 : PUSH 12
1 : PUSH 8
2 : JEQ 8
3 : JLT 6
4 : SUB
5 : JUMP 2
6 : SWAP
7 : JUMP 2
8 : STOP
</pre>

</div>

</div>

<div id="outline-container-4" class="outline-2">
<h2 id="sec-4">Input file format</h2>
<div class="outline-text-2" id="text-4">

<p>
Java bytecode program are encoded in binary form, which are relatively
hard and tedious to decode. Hence, we have made things much simpler by
encoding the mini-Bytecode in Ascii form, rather than in binary form.
</p>
<p>
First, integers will be encoded as a character. Here <i>ord</i> maps a character to a number according to 
<a href="./ASCII.html">ASCII chart</a>. And <i>chr</i> is the opposite of <i>ord</i>.
</p>
<p>
encInteger <i>i</i> = chr(ord "0" + <i>i</i>)
</p>
<p>
So, 1,2,3 will be encoded as "1","2","3" and 41,42,43 as "Y","Z","[".
</p>
<p>
The encoding of all the instructions is defined as function <b>enc</b>. Here ^ means to concatenate two strings.
"a" ^ "b" = "ab".
</p>
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
<caption></caption>
<colgroup><col align="left" /><col align="left" />
</colgroup>
<tbody>
<tr><td>enc(pop)</td><td>"p"</td></tr>
<tr><td>enc(add)</td><td>"+"</td></tr>
<tr><td>enc(sub)</td><td>"-"</td></tr>
<tr><td>enc(swap)</td><td>"s"</td></tr>
<tr><td>enc(push <i>i</i>)</td><td>"c" ^ encInteger(<i>i</i>)</td></tr>
<tr><td>enc(jump <i>i</i>)</td><td>"j" ^ encInteger(<i>i</i>)</td></tr>
<tr><td>enc(jeq <i>i</i>)</td><td>"=" ^ encInteger(<i>i</i>)</td></tr>
<tr><td>enc(jlt <i>i</i>)</td><td>"&lt;" ^ encInteger(<i>i</i>)</td></tr>
<tr><td>enc(load <i>i</i>)</td><td>"r" ^ encInteger(<i>i</i>)</td></tr>
<tr><td>enc(store <i>i</i>)</td><td>"w" ^ encInteger(<i>i</i>)</td></tr>
<tr><td>enc(stop)</td><td>"."</td></tr>
</tbody>
</table>


<p>
For example, the program showed in previous section is encoded as "c&lt;c8=8&lt;6-j2sj2.".
</p>
</div>

</div>

<div id="outline-container-5" class="outline-2">
<h2 id="sec-5">How mini-JVM runs? </h2>
<div class="outline-text-2" id="text-5">

<p>A mini-Bytecode program is a list of instructions and 
we mark them from 0 as showed in <a href="#sec-3">section 2</a>.
The machine state during the execution is <code>(stack, store, pc)</code>. Here
<b>stack</b> is the data stack, 
<b>store</b> is a memory containing all variables, <b>pc</b> 
is the program counter (i.e., the next instruction in the instructions 
list to be executed). For example, ([1,2], [0:12,1:8], 3) 
means we have a stack of [1,2] , a store mapping variable 0 to 12
and variable 1 to 8, and we are going to execute the 3rd instruction.
</p>
<p>
Suppose that before an instruction <code>instr</code> executes, the
machine state is <code>([x, y, ...], store, pc)</code> (remember that
now <code>pc</code> points to <code>instr</code>), 
we describe the effect of executing the instruction <code>instr</code>
in the table below.
</p>
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
<caption></caption>
<colgroup><col align="left" /><col align="left" />
</colgroup>
<thead>
<tr><th scope="col">Instruction</th><th scope="col">Machine state after execution</th></tr>
</thead>
<tbody>
<tr><td>pop</td><td>([y,&hellip;],var,pc+1)</td></tr>
<tr><td>add</td><td>([(x+y),y,&hellip;],var,pc+1)</td></tr>
<tr><td>sub</td><td>([(x-y),y,&hellip;],var,pc+1)</td></tr>
<tr><td>swap</td><td>([y,x,&hellip;],var,pc+1)</td></tr>
<tr><td>push <i>i</i></td><td>([i,x,y,&hellip;],var,pc+1)</td></tr>
<tr><td>jump <i>i</i></td><td>([x,y,&hellip;],var,i)</td></tr>
<tr><td>jeq <i>i</i></td><td>if x=y then ([x,y,..],var,i) else ([x,y,&hellip;],var,pc+1)</td></tr>
<tr><td>jlt <i>i</i></td><td>if x&lt;y then ([x,y,..],var,i) else ([x,y,&hellip;],var,pc+1)</td></tr>
<tr><td>load <i>i</i></td><td>([var(i),x,y,&hellip;],var,pc+1)</td></tr>
<tr><td>store <i>i</i></td><td>([y,&hellip;],update var(i) to be x,pc+1)</td></tr>
<tr><td>stop</td><td>([x,y,..],var,pc)</td></tr>
</tbody>
</table>


<p>
The initial mathine state is <code>([], [], 0)</code>, which
means an empty stack and store, and we run from the 0th instruction. 
Program stops when we reach <code>stop</code>, and the top element
on stack is treated as the final result.
</p>
<p>
For example, the program in <a href="#sec-3">section 2</a> will execute as below. And the result is 4.
</p>
<table border="2" cellspacing="0" cellpadding="6" rules="groups" frame="hsides">
<caption></caption>
<colgroup><col align="left" /><col align="left" />
</colgroup>
<tbody>
<tr><td>PUSH 12</td><td>([12 ],[ ],1)</td></tr>
<tr><td>PUSH 8</td><td>([8,12],[ ],2)</td></tr>
<tr><td>JEQ 8</td><td>([8,12],[ ],3)</td></tr>
<tr><td>JLT 6</td><td>([8,12],[ ],6)</td></tr>
<tr><td>SWAP</td><td>([12,8],[ ],7)</td></tr>
<tr><td>JUMP 2</td><td>([12,8],[ ],2)</td></tr>
<tr><td>JEQ 8</td><td>([12,8],[ ],3)</td></tr>
<tr><td>JLT 6</td><td>([12,8],[ ],4)</td></tr>
<tr><td>SUB</td><td>([4,8],[ ],5)</td></tr>
<tr><td>JUMP 2</td><td>([4,8],[ ],2)</td></tr>
<tr><td>JEQ 8</td><td>([4,8],[ ],3)</td></tr>
<tr><td>JLT 6</td><td>([4,8],[ ],6)</td></tr>
<tr><td>SWAP</td><td>([8,4],[ ],7)</td></tr>
<tr><td>JUMP 2</td><td>([8,4],[ ],2)</td></tr>
<tr><td>JEQ 8</td><td>([8,4],[ ],3)</td></tr>
<tr><td>JLT 6</td><td>([8,4],[ ],4)</td></tr>
<tr><td>SUB</td><td>([4,4],[ ],5)</td></tr>
<tr><td>JUMP 2</td><td>([4,4],[ ],2)</td></tr>
<tr><td>JEQ 8</td><td>([4,4],[ ],8)</td></tr>
<tr><td>STOP</td><td>([4,4],[ ],8)</td></tr>
</tbody>
</table>



<div id="outline-container-3" class="outline-2">
<h2 id="sec-3">Handin</h2>
<div class="outline-text-2" id="text-3">

To handin this lab, you should make sure that your files are
compilable by MLton, and result form is <code>"Result:***"</code>.

<p>
The last thing to note is that you should not change the file name
of <code>jvm.mlb</code> (but you can modify its content).



</div>
</div>
<div id="postamble">
</div>
</div>
</body>
</html>
